Discrete-time quantum walks^[1] (DTQW) are quantum-mechanical generalizations of the classical random walk (CRW). Their hallmark property is that on a regular lattice they spread quadratically faster than random walks, i.e., ballistically rather than diffusively.^[2] This property makes them useful in quantum search algorithms,^[3] or even for general quantum computing.^[4] So far, we have realized quantum walks on trapped ions,^[5–7] cold atoms in optical lattices,^[8–10] and light on an optical table.^[11–16] Furthermore, there are many other experimental proposals.^[17,18]

The evolution of a quantum walk is given by iterations of a unitary time step operator, which can always be written in the form U = e^−iH_eff, with H_eff being a Hermitian operator. In this sense, a quantum walk is a stroboscopic simulator of an effective Hamiltonian H_eff. This is a powerful theoretical concept that allows much of the physical intuition about lattice systems to be applied to quantum walks. As an example, consider quantum walks on regular lattices: the maximum of the group velocity of the effective Hamiltonian translates directly to the velocity of ballistic expansion of the walk. In the presence of static (time-independent) disorder, quantum walks can lose their advantage over random walks in terms of the speed of spreading: they can undergo Anderson localization, whereby the mean-squared distance of the walker from the origin stays bounded even in the infinite-time limit. Besides theoretical,^[19,20] and numerical studies,^[21] this effect has also been observed experimentally.^[22]

There have been a number of papers analyzing the Anderson localization on infinite quantum walks.^[23–30] We know from a lot of investigations that the static disorder makes infinite quantum walks suffer from the Anderson localization. But from a practical perspective, the real-world network is finite and has a boundary. The effect caused by the static disorder in finite quantum walks may be different from that in infinite quantum walks. For example, on one-dimensional (1D) graphs the left wavefront of the quantum walker has the chance to interfere with the right wavefront because of the boundary. Therefore, we need deeper researches on the effect caused by the static disorder on the finite network.

In the present work, we firstly introduce the localization of discrete-time quantum walks on one-dimensional infinite graphs. Then we quantitatively analyze the probability distribution difference between infinite and finite cases in the presence of the same static disorder. We vectorize the probability distributions of quantum walks on both one-dimensional infinite and finite graphs and then show the distribution difference by computing out their distance. We will analyze this difference on two variables, i.e., the boundary condition (the number of nodes in the finite graph) and the number of steps taken, and find out the patterns. The result can be extended to higher dimensional cases.

The structure of the present paper is organized as follows. In Section 2, we introduce the Anderson localization of quantum walks on the one-dimensional infinite graph. In Section 3, we analyze the localization of quantum walks on the one-dimensional finite graphs in the presence of the static disorder by comparing its probability distribution with that in the infinite case. Finally, we give our conclusion in the last section.

Quantum walks derive from classical random walk and are also widely studied in two forms, continuous-time QW (CTQW),^[31] and discrete-time QW (DTQW).^[32–35] They are found to have very valuable applications in quantum algorithms.^[36–39] DTQW also has two cases: a quantum walker walks on infinite graphs and on finite ones. In this paper, we call DTQW on infinite graphs IDTQW and DTQW on finite graphs FDTQW.

The discrete-time quantum walk, whose dynamics f can be controlled by the quantum coin operation, is used for the study presented in this paper. It has two components, i.e., a particle consisting of a two-face coin (a qubit) in the Hilbert space spanned by | 0〉 and | 1〉, and a walker evolving on spatial positions, whose degree of freedom is in the Hilbert space spanned by | x〉, where x ∈ G, a specific group. In IDTQW, G is the set ℤ of integers. In FDTQW G is ℤ_n satisfying modulo n operation. Physically, it means node x and node y represent the same node if x ≡ y(mod n). A t-step DTQW evolution with unit time in each step of the walk is generated by iteratively applying a unitary operation U on the Hilbert space :

The probability to find the particle at site x after 3t steps is given by

The standard IDTQW evolutions have been studied in a series of investigations. In this model, we use an identical coin operation in each step and its probability distribution shows a periodic pattern. For example, a walker evolves in one-dimensional line using an unbiased coin operation, that is, T_ξ,θ,ς with parameters ξ = ς = 0. When changing the parameters ξ, θ, ς in the coin operation during each step, however, this periodic order can be broken down, resulting in many amazing results, in which Anderson localization is one of the most important. Many papers have numerically and theoretically studied this localization.^[23–30] But they imply the dynamic of the walker evolves on infinite graphs, i.e., the case when group G is the set ℤ of integers. Hence, we need deeper study upon the effect of boundary conditions on the localized effect of quantum walks on a finite graph out of practical reasons.

Firstly, we introduce the Anderson localization of quantum walks on a one-dimensional infinite graph. We will consider a different set of coin operations. Evolution of IDTQW using disordered coin operation can be modelled by randomly choosing a quantum coin operator in the U(2) group for each step, i.e.,

Fig. 1.

Figure Option ViewDownloadNew Window

Fig. 1. Comparison of the probability distribution of the IDTQW evolved by assigning quantum coin operation in a U(2) group with random parameters in a different range to each step of the walk to that of the Hadamard walk. Curve a: the walk using parameters assigned from ξ, ς ∈ {0, π/2} and θ ∈ {π/4, π/2}; curve b: the walk using parameters assigned from ξ, ς ∈ {0, π/2} and θ ∈ {0, π/4}; curve c: the walk using parameters assigned from ξ, θ, ς ∈ {0, π/2} for Tξ,θ,ς; curve d Hadamard walk, which is the standard form of the IDTQW with identical coin (θ = π/4); curve e the walk using T0,π/8,0. Localization is seen in the case of curve (a). The distribution is after 200 steps of the walk on a particle with initial state at origin We could see in case a the quantum walks suffer from localization.

However, the probability distribution is quite different when using non-identical coin operations. By limiting the range of the three coin parameters the probability distribution can be localized or diffused in spatial space. In case c, the three coin parameters are randomly chosen from a complete range {0, π/2}. But we can see different phenomena by further restricting the range of parameter θ. When using θ ∈ {0, π/4} while other parameters are still picked from the complete range {0, π/2}, the IDTQW will diffuse in spatial space without any sharp peaks when compared with the standard IDTQW evolution.^[30] The walk using θ ∈ {π/4, π/2}, however, localizes its distribution around the origin.^[27] In our numerical simulations, the parameters θ, ξ, and ς are generated from a random number generator in each step with equal probable appearance of any number in the corresponding specific ranges.

In order to analyze the localization of quantum walks on one-dimensional finite graphs in the presence of static disorder, we compare the probability distribution on finite graphs with the familiar localization on infinite graphs. Firstly we vectorize the probability distribution in both one-dimensional finite graphs and infinite cases. Then compute out the distance between these vectors to quantitatively analyze the localization difference. Surely both the finite and infinite cases share the same parameters of the evolution operator, i.e., the same static disorder, except for different boundary conditions.

3.1. Vectorize the probability distribution of quantum walks in both finite and infinite graphs

The probability vector of quantum walks on the one-dimensional infinite graph on line is obtained as follows: suppose the walker takes N steps in line, the walker will be bounded within −N and N with probability zero at other nodes out of this range. We set the probabilities in the (2N+1) nodes as entries of the probability vector. For example, the walker sets off from node 0 and walks 100 steps. The furthest nodes that the walker reaches are 100 and −100 and the walker will be bounded within −100 and 100. The probability amplitude out of this range is 0. We set the probability distribution within node −100 and 100 as a 201-dimensional probability vector.

For the finite case, i.e, the quantum walks on a circle, the walker still takes N steps but the number of nodes n in the circle is n < (2N + 1). Then its left wavefront and right wavefront will interfere with each other, thus having effects on the probability distribution. In order to estimate the probability distribution difference between IDTQW and FDTQW in the presence of the static disorder, we should transform this n circle to a (2N + 1) line so that their probability vectors have the same dimension. The specific approach is described as follows: the conventional labels of nodes in the circle are from 0 to (n − 1), in which node 0 is the origin of the walks and nodes 1 and (n − 1) are adjacent to node 0. Then we relabel the nodes. If n is odd, the labels of nodes from 0 to (n − 1)/2 are unchanged (half the number of the nodes) and these nodes are on the right side of the origin, but the labels of nodes from (n − 1) to (n + 1)/2 (the other half) are relabeled from −1 to (1 − n)/2 and these nodes are on the left sides of the origin. We cut the connection between node (n − 1)/2 and the relabeled node (1 − n)/2 and obtain the corresponding n line. Finally we extend this n line to a (2N + 1) line by adding extra nodes on its left and right sides so that we align the origins in finite and infinite cases. In order to satisfy the condition that the probabilities of entries in the larger line sum to one, we set the probabilities on the extra entries to zero and achieve our purpose: extending the n probability vector to (2N + 1) one. If n is even, the labels of nodes from 0 to (n/2) are unchanged, but the labels of nodes from (n − 1) to (n/2 + 1) are relabeled as those from −1 to (−n/2 + 1) and we obtain the (2N + 1) probability vector by following the same method used in the odd case.

We can see that in the even case the number of nodes on the right side is one more than that on the left side. We could also divide this circle so that the left side has one more node. But when the number of nodes is large, this small distinction has a little difference on the distance and thus on the final result.

In the following Fig. 2 we show an example when the walker takes 4 steps and the circle has 5 nodes.

Fig. 2.

Figure Option ViewDownloadNew Window

Fig. 2. An example to visualize how to vectorize the probability distribution. The walker takes 4 steps. In this example, the probability distribution of quantum walks on an infinite graph is shown in the figure and we vectorize the probability distribution as (0.17032, 0, 0.0834, 0, 0.25794, 0, 0.35851, 0, 0.12983). Also according to the approach raised above, we vectorize the probability distribution of quantum walks on a finite graph as (0, 0, 0.24286, 0.04181, 0.35087, 0.04297, 0.32149, 0, 0).

3.2. Compute out the distance between the probability distributions of quantum walks on one-dimensional finite graph and one-dimensional infinite graph in the presence of the same static disorder

In our simulation, the coin operator and shift operator share the same parameters in both the IDTQW and FDTQW. To be specific, we choose the parameters ξ, ς ∈ {0, π/2}, θ ∈ {π/4, π/2} so that the quantum walker localizes on infinite graphs. The initial state of the quantum walker is In order to do a comprehensive comparison between infinite and finite cases, we set two variables: steps taken and the boundary conditions, i.e., the number of nodes in finite graphs.

In Table 1, N represents the number of steps taken. n stands for the number of nodes in the finite graphs and we choose it so that the nodes number is dependent on the number of steps taken. We choose different one-dimensional finite graphs and the nodes number gap is 1/8N. When steps taken is fixed, we make use of the approach introduced in Subsection 3.1 to vectorize the probability distribution of quantum walks in infinite and finite graphs and compute out the Euclidean distance between them. We quantitatively analyze the vector distances under different steps taken and different one-dimensional finite graphs, i.e., different boundary conditions. The detailed steps taken and the number of nodes chosen are shown in the following table (Table 1).

Table 1.

Table 1.

Table 1. The number of steps taken in our calculations. .

Table 1. The number of steps taken in our calculations. .

The simulation result shows that when the steps taken are constant, the probability distribution of quantum walks on finite graphs tends to the localization in the infinite case with the increase of the number of nodes in FDTQW, and when the number of nodes in FDTQW remain the same scale, e.g., 1/16N, the probability distribution of quantum walks on finite graphs is increasingly close to the localization in the infinite case with the increase of steps taken. When the number of steps taken is small, the tight boundary conditions (the number of nodes is relatively small) have a great effect on the probability distribution difference. For example, the simulation result shows that the distance is 0.2428 when the steps taken are 32 and the number of nodes is 3/16N. In this case, we could not judge whether quantum walks on one-dimensional graphs suffer from localization. Amazingly, when the steps taken are large enough (in our simulation, roughly larger than 512) or the boundary conditions are loose (in our simulation, the number of nodes is larger than 1/2N), the distance is negligible (less than 0.05). It means in the presence of the same static disorder quantum walks on one-dimensional finite graphs suffer from the same localization as that in the infinite case under these two conditions. We can understand this phenomenon as that the left wavefront has little chance to interfere with the right wavefront. The changing tendency of the distance with the changes of steps and number of nodes are shown in Fig. 3.

Fig. 3.

Figure Option ViewDownloadNew Window

Fig. 3. This figure more specially shows the changing tendency of the distance with the changes of the two variables: steps taken and number of nodes. The gap between the steps taken is 32 steps and that of the number of nodes is 1/16N. We can see clearly that the probability distribution of FDTQW tends to the localization in the infinite case with the increase of steps taken and also with the increase of the number of nodes in FDTQW. Amazingly, when the steps taken are large enough or the boundary conditions are loose, e.g., the number of nodes is larger than 1/2N, the distance is negligible. It means quantum walks on one-dimensional finite graphs also suffer from localization even under boundary conditions.

To consider the localization of quantum walks in a better real-world set, we have discussed the difference in probability distribution between quantum walks on a line and on a finite graph in the presence of the same static disorder. We introduced an IDTQW model in which a random coin is assigned to each step of the walk to break the periodicity during the evolution.

By picking the coin operation from a different range of parameters, we have shown that the IDTQW on a two-state particle can be strongly localized in position space. Furthermore, we have given the approach to vectorize the probability distribution in both IDTQW and FDIQW. This approach enables us to get a glimpse of the probability distribution difference of quantum walks between the infinite and finite cases in the presence of static disorder. Through the differences, we find the amazing result that when the steps taken are large, or the boundary conditions are loose, the quantum walks on one-dimensional finite graphs also suffer from the same localization as that in the infinite case. It means the left wavefront has no chance to interfere with the right wavefront under the boundary conditions when walker evolves on finite graph. In general this result can be extended to higher dimensions.